﻿public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
    {
        // 计算两个链表的长度
        int lenA = 0, lenB = 0;
        ListNode tmpA = headA, tmpB = headB;
        while (tmpA is not null)
        {
            lenA++;
            tmpA = tmpA.next;
        }
        
        while (tmpB is not null)
        {
            lenB++;
            tmpB = tmpB.next;
        }

        if (lenB > lenA)
        {
            for (int i = 0; i < lenB - lenA; i++)
            {
                headB = headB.next;
            }
        }
        else
        {
            for (int i = 0; i < lenA - lenB; i++)
            {
                headA = headA.next;
            }
        }
        
        // 开始判断交点
        while (headB is not null && headA is not null)
        {
            if (headA == headB)
            {
                return headA;
            }

            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }

    public static void Main(string[] args)
    {
        int[] listA = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5];
        int skipA = 2, skipB = 3;
        ListNode A = new ListNode(0), B = new ListNode(0);
        ListNode tmp;
        ListNode preA = A;
        for (int i = 0; i < skipA; i++)
        {
            tmp = new ListNode(listA[i]);
            preA.next = tmp;
            preA = tmp;
        }
        ListNode preB = B;
        for (int i = 0; i < listB.Length; i++)
        {
            tmp = new ListNode(listB[i]);
            preB.next = tmp;
            preB = tmp;

            if (i == skipB)
            {
                preA.next = preB;
            }
        }
        
        // 找到第一个交点
        Solution solution = new Solution();
        ListNode interNode = solution.GetIntersectionNode(A.next, B.next);
        Console.WriteLine(interNode.val);
        
        // 打印
        // ListNode tmpA = A.next, tmpB = B.next;
        // while (tmpA is not null)
        // {
        //     Console.Write($"{tmpA.val} ");
        //     tmpA = tmpA.next;
        // }
        // Console.WriteLine();
        // while (tmpB is not null)
        // {
        //     Console.Write($"{tmpB.val} ");
        //     tmpB = tmpB.next;
        // }
    }
}